package 剑指Offer._5160;

import general_class.TreeNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/17 11:17
 * 平衡二叉树
 * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 * 算法：二叉树 + 深度优先搜索
 * 后序遍历
 * 分别计算节点左子树和右子树的深度
 * 比较得到的深度，如果不满足，则返回 -1，提前结束 --- 剪枝
 * 反之，返回该节点的深度
 */
public class _55II {

    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }
    int dfs(TreeNode node) {
        if (node == null) return 0;
        int l = dfs(node.left);
        if (l == -1) return -1;
        int r = dfs(node.right);
        if (r == -1) return -1;
        return Math.abs(l - r) < 2 ? Math.max(l, r) + 1 : -1;
    }

}
